package com.utils;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BST {
	/**
	 * Binary search tree node
	 * <p/>
	 * data area --- generic Comparable height --- height within the tree of
	 * THIS node size --- number of nodes in this (sub)tree util ---
	 * miscellaneous int value, should we every need it left link --- left
	 * subtree right link --- right subtree
	 * <p/>
	 * The outer class has full access to this embedded class's fields.
	 */
	public static class BSTnode {
		public Comparable data; // Realistic case, this could be quite large
		int height; // Height of THIS NODE
		int size; // Number of nodes in this (sub)tree
		int util; // Generic utility area for an int value
		BSTnode left, // "<" subtree
				right; // ">" subtree

		BSTnode(Comparable data) // Constructor for leaf node
		{
			this.data = data;
			this.height = 0; // Leaf node has height zero
			this.size = 1;
			this.left = null;
			this.right = null;
		}
	}

	// Instance fields:

	protected BSTnode root = null, current = null; // Spare reference for
													// processing
	private int nItems; // Used in the protected tree walk
	private BSTnode free = null; // nodes for re-use

	// Class fields:

	// ? ? Show nodes on recycling ? ?
	protected static final boolean DEBUG = false;
	// ? ? Enforce unique keys ? ?
	protected static final boolean UNIQUE = false;

	// no constructor needed: root and free initialized to null already

	// ************** Over-all tree characteristics ************** //
	/*
	 * Tree size --- available as root.size, if there is a root
	 */
	public int size() {
		return root == null ? 0 : root.size;
	}

	/*
	 * Tree height == number of levels in the tree = root height
	 */
	public int height() // root = null means empty = -1
	{
		return root == null ? -1 : root.height;
	}

	/*
	 * Average node depth
	 */
	public double avgDepth() {
		if (root == null) {
			return -1; // Root as level zero forces this
		} else // root as level zero goes here
		{
			return sumDepths(root, 0) / root.size;
		}
	}

	// Total all depths of nodes within the tree:
	double sumDepths(BSTnode node, int deep) {
		if (node == null) {
			return 0; // Empty node does not contribute
		} else {
			return deep + sumDepths(node.left, deep + 1)
					+ sumDepths(node.right, deep + 1);
		}
	} // end sumDepths()

	// //******************* Simple Find *******************////

	/**
	 * Find the cell with the data field corresponding to Value
	 */
	Comparable find(Comparable value) {
		current = root;
		while (current != null && !current.data.equals(value)) {
			if (value.compareTo(current.data) < 0) {
				current = current.left;
			} else {
				current = current.right;
			}
		}

		return current == null ? null : current.data;
	}

	private void traverse(List<BSTnode> sortedList, BSTnode node) {
		if (node == null) {
			return;
		}
		traverse(sortedList, node.left);
		sortedList.add(node);
		traverse(sortedList, node.right);
	}

	private int binSearch(List<BSTnode> sortedList, Comparable val) {
		int min = 0;
		int max = sortedList.size() - 1;
		int med = 0;
		Comparable v1;
		Comparable v2;
		while (min <= max) {
			med = (min + max) / 2;
			v1 = sortedList.get(med).data;

			if (v1.compareTo(val) == 0) {
				return med;
			}
			if (v1.compareTo(val) < 0) {
				if (med == sortedList.size() - 1) {
					v2 = v1;
				} else {
					v2 = sortedList.get(med + 1).data;
				}
			} else {
				if (med == 0) {
					v2 = v1;
				} else {
					v2 = sortedList.get(med - 1).data;
				}
			}

			if (v1.compareTo(val) < 0) {
				// v1 < val
				if (v2.compareTo(val) > 0) {
					return med;
				} else if (v2.compareTo(val) == 0) {
					return med + 1;
				} else {
					// v1 < val && v2 < val
					if (min == med) {
						return Integer.MAX_VALUE;
					}
					min = med;
				}
			} else {
				// v1 > val
				if (v2.compareTo(val) < 0) {
					return med;
				} else if (v2.compareTo(val) == 0) {
					return med - 1;
				} else {
					// v2 > val && v1 > val
					if (max == med) {
						return Integer.MIN_VALUE;
					}
					max = med;
				}
			}
		}
		return med;
	}

	/**
	 * Range Search
	 * 
	 * @param min
	 * @param max
	 * @return
	 */
	public Set<BSTnode> rangeFind(Comparable min, Comparable max) {
		Set<BSTnode> range = new HashSet<BSTnode>();
		List<BSTnode> sortedList = new ArrayList<BSTnode>();
		traverse(sortedList, root);
		int left = binSearch(sortedList, min);
		if (left > 0) {
			left--;
		}
		int right = binSearch(sortedList, max);
		if (right < sortedList.size() - 1) {
			right++;
		}
		if (left == Integer.MAX_VALUE && right == Integer.MIN_VALUE) {
			return range;
		} else if (left == Integer.MIN_VALUE && right == Integer.MAX_VALUE) {
			range.addAll(sortedList);
			return range;
		} else {
			for (int k = Math.max(left, 0); k <= Math.min(
					sortedList.size() - 1, right); k++) {
				range.add(sortedList.get(k));
			}
		}
		return range;
	}

	// ************** Tree modifier methods ************** //
	/*
	 * Empty out the tree. The "autumn" method recycles the nodes to save on
	 * garbage collection expense.
	 */
	public void clear() {
		autumn(root);
		root = null;
	}

	// All the leaf (nodes) fall . . . recursively
	void autumn(BSTnode node) {
		if (node != null) {
			autumn(node.left); // post-order traversal
			autumn(node.right);
			recycle(node); // This is now a leaf. Goodbye!
		}
	} // end autumn()

	/*
	 * Insertion in the BST
	 */
	// Insert the value into its proper place in the binary search tree
	public void insert(Comparable value) {
		root = insert(root, value);
	}

	// Recursive insertion, returning reference to subtree generated.
	BSTnode insert(BSTnode node, Comparable value) {
		if (node == null) {
			node = build(value);
		} else if (value.compareTo(node.data) < 0) {
			node.left = insert(node.left, value);
		}
		// ***** If equal keys allowed, place them right *****
		else if (!UNIQUE) {
			node.right = insert(node.right, value);
		}
		// ***** Equal keys must be FORBIDDEN *****
		else if (value.compareTo(node.data) > 0) {
			node.right = insert(node.right, value);
		}
		// ***** If equal keys are NOT allowed, ERROR *****
		else {
			System.err.println(value + " is already in.");
		} // end if/else if/else if/else if/else
			// Correct this node's height and size after the insertion.
			// The correction propagates upwards in the recursive call stack.
		node.height = newHt(node);
		node.size = newSize(node);
		return node;
	} // end insert(BSTnode, Comparable)

	// ******************* Deletion ******************* ///

	// Fields required as stable in delete(BSTnode, int)
	BSTnode deleteNode, lastNode;

	/*
	 * Delete the node with the value passed.
	 */
	public void delete(Comparable value) {
		deleteNode = null;
		lastNode = null;
		root = delete(root, value);
	}

	// Interchange the .data fields on two BSTnodes passed
	static void swapData(BSTnode d, BSTnode s) {
		Comparable temp = d.data;
		d.data = s.data;
		s.data = temp;
	}

	BSTnode delete(BSTnode node, Comparable value) {
		if (node == null) {
			return null;
		}

		lastNode = node; // Reference to LAST node seen
		if (value.compareTo(node.data) < 0) {
			node.left = delete(node.left, value);
		} else {// When we FIND the node and take one step right, all subsequent
			// steps will be left --- down to the in-order successor
			deleteNode = node; // Potentially the node to go
			node.right = delete(node.right, value);
		}

		// In the returns, the call where we are dealing with the replacement
		if (node == lastNode) {// Check to see if we indeed DID find the value
			if (deleteNode != null && value.equals(deleteNode.data)) {// Final
																		// check:
																		// if
																		// node
																		// is
																		// RIGHTMOST
																		// in
																		// its
																		// subtree
				if (deleteNode == lastNode) // Half-nodes are easy!
				{
					node = node.left; // Return left subtree
				}
				// node is NOT rightmost in its subtree. Copy replacement up.
				else {
					swapData(deleteNode, lastNode);
					node = node.right; // Return right subtree
				}
				recycle(lastNode); // Return the node for re-use
			}
		} else // Adjust heights on the way back up the recursive stack
		{
			node.height = newHt(node);
			node.size = newSize(node);
		}
		return node;
	}

	// ******************* Recursive traversal ******************* //
	/*
	 * Walk through the tree; display is to be ascending order
	 */
	public void walk() {
		if (root != null) {
			nItems = 0;
			inOrder(root);
			// Check whether final '\n' is required.
			if (nItems % 10 != 0) {
				System.out.println();
			}
		}
	} // end walk()

	// To get ascending order, do an in-order traversal of the tree
	void inOrder(BSTnode item) {
		if (item == null) {
			return; // I.e., empty tree
		}

		inOrder(item.left); // Process left sub-tree
		System.out.printf("%4s(%d)", item.data, item.height);
		if (++nItems % 10 == 0) {
			System.out.println();
		}
		inOrder(item.right); // Process right sub-tree
	}

	// ******************* NON-Recursive traversal ******************* //
	/*
	 * Display the BST horizontally --- based on a level-order traversal
	 */
	// Keep track of position on the line across calls to setPos
	static int skip;

	public void pretty() {
		skip = 0;

		if (root == null) // Nothing to display!
		{
			System.out.println("Empty tree!");
			return;
		}

		setPos(root); // Find line position for each node
		pretty(root); // level-order traversal displaying the nodes
	} // end pretty() // one line for each level, in proper position

	// Find line position for each node --- based on in-order traversal
	void setPos(BSTnode node) {// If the nodes were all printed on one line,
								// their order is based
		// on an in-order traversal. skip shows number of positions to skip
		// to properly position the node. Note that this MUST be a class
		// data member --- the root depends on skip to come back with the
		// size of the entire left subtree, for instance.
		if (node != null) {
			setPos(node.left);
			node.util = skip; // Store skip value in util data member
			skip += 2; // Update for printing THIS node
			setPos(node.right);
		} // end if
	} // end setPos()

	// We need to retain information on tree level in a queue of BSTnodes.
	static class Wrapper {
		int level;
		BSTnode node;

		Wrapper(BSTnode node, int level) {
			this.level = level;
			this.node = node;
		}
	}

	// Pretty-print: each tree level prints on one line, with the node
	// horizontally positioned to be visually the parent of its children.
	void pretty(BSTnode node) {// work queue during traversal
		Deque<Wrapper> queue = new ArrayDeque<Wrapper>();

		int position = 0, // position in output line
		level = 1, // level being processed
		current; // value for node ABOUT to process

		// level-order traversal: initialize the work queue with the root
		queue.offer(new Wrapper(node, level));// node initially IS the root

		while (!queue.isEmpty()) // Go there's nothing left to do!
		{
			Wrapper item = queue.remove();
			node = item.node;
			current = item.level;
			if (node.left != null) // Enqueue child nodes
			{
				queue.offer(new Wrapper(node.left, current + 1));
			}
			if (node.right != null) {
				queue.offer(new Wrapper(node.right, current + 1));
			}
			// Check for line-break: change in tree level
			if (current != level) {
				System.out.println();
				position = 0;
				level = current;
			}
			// skip over to proper position
			for (; position < node.util; position++) {
				System.out.print(" ");
			}
			System.out.printf("%2s", node.data);
			position += 2; // Update position for the output just done
		} // end while
		System.out.println(); // Final line termination.
	} // end pretty(BSTnode)

	// ******************* Utility functions ******************* //

	// Return the height based on the children; node must NOT be null.
	static int newHt(BSTnode node) {
		BSTnode lt = node.left, rt = node.right;

		if (lt == null && rt == null) // Leaf node is height zero
		{
			return 0;
		} else if (lt == null) // Half node cases
		{
			return 1 + rt.height;
		} else if (rt == null) {
			return 1 + lt.height;
		} else // Full node --- need java.lang.Math.max
		{
			return 1 + Math.max(lt.height, rt.height);
		}
	} // end newHt()

	// Return the size based on the children; node must NOT be null.
	static int newSize(BSTnode node) {
		BSTnode lt = node.left, rt = node.right;

		if (lt == null && rt == null) // Leaf node has size 1
		{
			return 1;
		} else if (lt == null) // Half node cases
		{
			return 1 + rt.size;
		} else if (rt == null) {
			return 1 + lt.size;
		} else // Full node --- do the sum
		{
			return 1 + lt.size + rt.size;
		}
	} // end newSize()

	// ************** free-space list mainenance ****************** //

	// Generate a node, either re-using from the free list or constructed
	BSTnode build(Comparable data) {
		BSTnode rtn;

		if (free == null) {
			rtn = new BSTnode(data);
			if (rtn == null) {
				System.err.println("ALLOCATION ERROR.  Abort execution.");
				System.exit(7);
			}
		} else {
			rtn = free;
			free = free.right;
			rtn.data = data;
			rtn.height = 0;
			rtn.size = 1; // Leaf node
			rtn.left = null;
			rtn.right = null;
		}
		return rtn;
	}

	// push node onto free list.
	void recycle(BSTnode node) {
		if (DEBUG) {
			System.out.println("Recycling node \"" + node.data + '"');
		}
		node.left = null;
		node.right = free;
		free = node;
	} // end recycle

} // end class BST

